#define _CRT_SECURE_NO_WARNINGS
#include"add.h"

void QueueInit(Que* pq) {
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}
void QueueDestroy(Que* pq) {
	assert(pq);
	QNode* cur = pq->head;
	while (cur) {
		QNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}
void QueuePush(Que* pq, DataSType x) {
	assert(pq);
	QNode* newnode =(QNode*)malloc(sizeof(QNode));
	if (newnode == NULL) {
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->head == NULL) {
		pq->head = pq->tail = newnode;
		pq->size++;
	}
	else {
		pq->tail->next = newnode;
		pq->tail = newnode;
		pq->size++;
	}
}

void QueuePop(Que* pq) {
	assert(pq);
	assert(pq->head != NULL);
	if (pq->head->next == NULL) {
		free(pq->head);
		pq->head = pq->tail = NULL;
		pq->size--;
	}
	else {
		QNode* tmp = pq->head->next;
		free(pq->head);
		pq->head = tmp;
		pq->size--;
	}
}
DataSType QueueFront(Que* pq) {
	assert(pq);
	assert(pq->size > 0);
	return pq->head->data;
}
DataSType QueueBack(Que* pq) {
	assert(pq);
	assert(pq->size > 0);
	return pq->tail->data;
}
bool QueueEmpty(Que* pq) {
	assert(pq);
	return pq->size == 0;
}
int QueueSize(Que* pq) {
	assert(pq);
	return pq->size;
}
void STInit(ST* ps) {
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

void STDestroy(ST* ps) {
	assert(ps);
	free(ps->a);
	ps->top = 0;
	ps->capacity = 0;
}

void STPush(ST* ps, DataSType x) {
	assert(ps);
	if (ps->top == ps->capacity) {
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		DataSType* tmp = (DataSType*)realloc(ps->a, sizeof(DataSType) * newcapacity);
		if (tmp == NULL) {
			perror("realloc failed");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void STPop(ST* ps) {
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

DataSType STTop(ST* ps) {
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

int STSize(ST* ps) {
	assert(ps);
	return ps->top;
}

bool STEmpty(ST* ps) {
	assert(ps);
	return ps->top == 0;
}

void SLTPrint(SLTNode* phead) {
	assert(phead);
	while (phead) {
		printf("%d->", phead->data);
		phead = phead->next;
	}
	printf("\n");
}

SLTNode* BuySListNode(DataSType x) {
	SLTNode* tmp = (SLTNode*)malloc(sizeof(SLTNode));
	if (tmp == NULL) {
		perror("malloc failed");
		exit(-1);
	}
	tmp->data = x;
	tmp->next = NULL;
	return tmp;
}

void SLTPushBack(SLTNode** pphead, DataSType x) {
	assert(pphead);
	SLTNode* tmp = BuySListNode(x);
	if (*pphead == NULL) {
		*pphead = tmp;
	}
	else {
		SLTNode* cur = *pphead;
		while (cur->next) {
			cur = cur->next;
		}
		cur->next = tmp;
	}
}

void SLTPushFront(SLTNode** pphead, DataSType x) {
	assert(pphead);
	SLTNode* tmp = BuySListNode(x);
	if (*pphead == NULL) {
		*pphead = tmp;
	}
	else {
		tmp->next = *pphead;
		*pphead = tmp;
	}
}

void SLTPopBack(SLTNode** pphead) {
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;
	}
	else {
		SLTNode* cur = *pphead;
		while (cur->next->next) {
			cur = cur->next;
		}
		free(cur->next);
		cur->next = NULL;
	}
}

void SLTPopFront(SLTNode** pphead) {
	assert(pphead);
	assert(*pphead);
	SLTNode* tmp = (*pphead)->next;
	free(*pphead);
	*pphead = tmp;
}

SLTNode* SLTFind(SLTNode* phead, DataSType x) {
	assert(phead);
	SLTNode* cur = phead;
	while (cur) {
		if (cur->data == x) {
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

void SLTDestroy(SLTNode** pphead) {
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur) {
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

void SLTInsert(SLTNode** pphead, SLTNode* pos, DataSType x) {
	assert(pphead);
	if (*pphead = pos) {
		SLTPushFront(pphead, x);
	}
	else {
		SLTNode* cur = *pphead;
		while (cur->next != pos) {
			cur = cur->next;
		}
		SLTNode* tmp = BuySListNode(x);
		tmp->next = cur->next;
		cur->next = tmp;
	}
}

void SLTInsertAfter(SLTNode* pos, DataSType x) {
	assert(pos);
	SLTNode* tmp = BuySListNode(x);
	tmp->next = pos->next;
	pos->next = tmp;
}

void SLTErase(SLTNode** pphead, SLTNode* pos) {
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur->next != pos) {
		cur = cur->next;
	}
	cur->next = pos->next;
	free(pos);

}

void SLTEraseAfter(SLTNode* pos) {
	assert(pos);
	SLTNode* tmp = pos->next;
	pos->next = pos->next->next;
	free(tmp);
}